
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
//    public int trap(int[] height) {
//        int n = height.length;
//        int res = 0;
//        for (int i = 0; i < n - 1; i++) {
//            int l_max = 0, r_max = 0;
//            // 找到最右边最高的柱子
//            for (int j = i; j < n; j++) {
//                r_max = Math.max(r_max, height[j]);
//            }
//            // 找到最左边最高的柱子
//            for (int j = i; j >= 0; j--) {
//                l_max = Math.max(l_max,height[j]);
//            }
//            // 如果自己height[i]就是最高的话
//            // l_max == r_max == height[i]
//            res += Math.min(l_max, r_max) - height[i];
//        }
//        return res;
//    }


    // 增加备忘录
//    public int trap(int[] height) {
//        if (height.length == 0) return 0;
//        int n = height.length;
//        int res = 0;
//
//        // 数组充当备忘录
//        int[] l_max = new int[n];
//        int[] r_max = new int[n];
//        // 初始化base case
//        l_max[0] = height[0];
//        r_max[n-1] = height[n-1];
//
//        // 从左向右计算l_max
//        for (int i = 1; i < n; i++) {
//            l_max[i] = Math.max(height[i], l_max[i-1]);
//        }
//        for (int i = n-2; i >=0; i--) {
//            r_max[i] = Math.max(height[i], r_max[i+1]);
//        }
//        for (int i = 1; i < n - 1; i++) {
//            res += Math.min(r_max[i], l_max[i]) - height[i];
//        }
//        return res;
//    }


    /**
     * 第一遍：双指针法
      */
//    public int trap(int[] height) {
//        int L = 0, R = height.length - 1;
//        int l_max = 0, r_max = 0;
//        int res = 0;
//        while (L < R) {
//            l_max = Math.max(l_max, height[L]);
//            r_max = Math.max(r_max, height[R]);
//            if (l_max < r_max) {
//                res += l_max - height[L];
//                L++;
//            } else {
//                res += r_max - height[R];
//                R--;
//            }
//        }
//        return res;
//    }


    /**
     * 第二遍
     * @param height
     * @return
     */
//    public int trap(int[] height) {
//        int L = 0, R = height.length - 1;
//        int l_max = 0, r_max = 0;
//        int res = 0;
//        while (L < R) {
//            l_max = Math.max(l_max, height[L]);
//            r_max = Math.max(r_max, height[R]);
//            if (l_max < r_max) {
//                res += l_max - height[L];
//                L++;
//            } else {
//                res += r_max - height[R];
//                R--;
//            }
//        }
//        return res;
//    }


    /**
     * 第三遍
     * @param height
     * @return
     */
//    public int trap(int[] height) {
//        int L = 0, R = height.length - 1;
//
//        int l_max = 0, r_max = 0;
//        int res = 0;
//        while (L < R) {
//            l_max = Math.max(l_max, height[L]);
//            r_max = Math.max(r_max, height[R]);
//            if (l_max < r_max) {
//                res += l_max - height[L];
//                L++;
//            } else {
//                res += r_max - height[R];
//                R--;
//            }
//        }
//        return res;
//    }


    /**
     * 第四遍 2/28
     * @param height
     * @return
     */

    public int trap(int[] height) {
        int L = 0, R = height.length - 1;

        // 定义左侧最大，和右侧最大
        int l_max = 0, r_max = 0;
        int res = 0;
        while (L < R) {
            l_max = Math.max(l_max, height[L]);
            r_max = Math.max(r_max, height[R]);
            if (r_max < l_max) {
                res += r_max - height[R];
                R--;
            } else {
                res += l_max - height[L];
                L++;
            }
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
